[PKUWC2018]Slay the Spire

2020-03-13
#组合数学 #动态规划Dp #数学
PKUWC

题意

有$n$张强化牌和$n$张攻击牌，强化牌权值为$\{a_i\}$，能使得后面的攻击伤害乘上$a_i$，攻击牌点数为$\{b_i\}$造成相应的伤害

随机在$2n$张牌里抽出$m$张，在$m$张牌里面以造成最大伤害的方式出$k$张牌，求所有情况下的伤害之和

$k\leq m\leq 2n\leq 3000$，对$998244353$取模，保证$a_i > 1$

题解

先考虑子问题，最优的情况一定是在至少出1张攻击牌的情况下出权值尽量大且尽量多的强化牌

如果能得知强化牌和攻击牌的情况，最后的答案容易合并

令$f_{i,j,0}$为前i张强化牌里面选j张的所有情况的积的和，$g_{i,j,0}$为前i张攻击牌里面选j张的所有情况的和的和

我们还要知道关于选择的最小值的情况，令$f_{i,j,1}$为前i张强化牌里面选j张且最小的是第i张的所有情况的积的和，$g_{i,j,1}$同理

答案分为强化牌选择是否足够$k-1$张来考虑

若不足$k-1​$，则贡献为$\sum f_{n,x, 0}\cdot g_{j,k-x, 1}\cdot \binom{n-j}{m-k}​$

若足够$k-1$，则贡献为$\sum f_{i,k-1,1}\cdot g_{j,1,1}\cdot \binom{2n-i-j}{m-k}$，这里$g_{j,1,1}$其实就是$b_j$

调试记录

刚好k-1的情况算了两遍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <cstdio>
#include <functional>
#include <algorithm>
#include <cctype>
#define LL long long
const int maxn = 3005;
const LL mo = 998244353;
using namespace std;
inline LL read(){
	LL x = 0; char ch = getchar();
	while (!isdigit(ch)) ch = getchar();
	while (isdigit(ch)) x = x * 10 + (ch & 15), ch = getchar();
	return x;
}
LL pow(LL x, LL t){
	LL res = 1; x %= mo;
	while (t > 0){
		if (t & 1) res = res * x % mo;
		x = x * x % mo;
		t >>= 1;
	}
	return res;
}
LL f[maxn][maxn][2], g[maxn][maxn][2];
LL fac[maxn], inv[maxn], a[maxn], b[maxn];
LL c[maxn][maxn];
LL C(int n, int m){
	if (m == 0 || m == n) return 1;
	if (m > n) return 0;
	return c[n][m];
	return 1ll * fac[n] * inv[m] % mo * inv[n - m] % mo;
}
int T, n, m, k;
int main(){
	scanf("%d", &T); int pre = 1;
	while (T--){
		scanf("%d%d%d", &n, &m, &k);
		for (int i = 1; i <= n; i++) a[i] = read(); sort(a + 1, a + n + 1, greater<LL>());
		for (int i = 1; i <= n; i++) b[i] = read(); sort(b + 1, b + n + 1, greater<LL>());
//		fac[0] = 1; for (int i = 1; i <= 2 * n; i++) fac[i] = fac[i - 1] * i % mo;
//		inv[2 * n] = pow(fac[2 * n], mo - 2);
//		for (int i = 2 * n - 1; i >= 1; i--) inv[i] = inv[i + 1] * (i + 1) % mo;
		c[0][0] = 1;
		for (int i = pre; i <= 2 * n; i++)
			for (int j = 0; j <= i; j++)
				c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mo;
		f[0][0][1] = 1; f[0][0][0] = 1;
		for (int i = 1; i <= n; i++){
			f[i][0][1] = 1ll;
			for (int j = 1; j <= i; j++){
				f[i][j][1] = (f[i - 1][j][1] + 1ll * a[i] * f[i - 1][j - 1][1] % mo) % mo;
				f[i][j][0] = 1ll * a[i] * f[i - 1][j - 1][1] % mo;
				g[i][j][1] = (g[i - 1][j][1] + 1ll * C(i - 1, j - 1) * b[i] % mo + g[i - 1][j - 1][1]) % mo;
				g[i][j][0] = (1ll * C(i - 1, j - 1) * b[i] % mo + g[i - 1][j - 1][1]) % mo;
			}
		} LL ans = 0;
		for (int x = 0; x < k - 1; x++)
			for (int j = 1; j <= n; j++)
				ans = (ans + 1ll * f[n][x][1] * g[j][k - x][0] % mo * C(n - j, m - k) % mo) % mo;
		for (int i = k - 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				ans = (ans + 1ll * f[i][k - 1][0] * b[j] % mo * C(n - i + n - j, m - k) % mo) % mo;
		printf("%lld\n", ans); pre = 2 * n;
	}
	return 0;
}